package solutions.leetcode.normal

import java.util.*

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/the-number-of-beautiful-subsets/">2597. 美丽子集的数目</a>
 */
private class Solution2597 {
    var ans = -1

    fun beautifulSubsets(nums: IntArray, k: Int): Int {
        val flag = IntArray(k * 2 + 1001)
        ans = -1
        dfs(nums, 0, k, flag)
        return ans
    }

    private fun dfs(nums: IntArray, i: Int, k: Int, flag: IntArray) {
        if (i >= nums.size) {
            ans++
            return
        }
        dfs(nums, i + 1, k, flag)
        val ind = nums[i] + k
        if (flag[ind - k] == 0 && flag[ind + k] == 0) {
            flag[ind]++
            dfs(nums, i + 1, k, flag)
            flag[ind]--
        }
    }
}

fun main() {
    val start = Calendar.getInstance().time.time
    println(Solution2597().beautifulSubsets(
        intArrayOf(
            18, 12, 10, 5, 6, 2, 18, 3
        ),
        8
    ))
    println(" --> ${Calendar.getInstance().time.time - start}")
}